package practice.sort;

/**
 * 希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] nums = {3, 9, 10, 2, 3, 123, 239, 4, 13, 443, 23, 29};
        sort(nums);
        for (int num :
                nums) {
            System.out.print(num + " ");
        }
    }

    public static void sort(int[] nums) {
        if (nums.length <= 0) {
            return;
        }
        int h = 1;
        while (h < nums.length / 3) {
            h = 3 * h + 1;
        }
        while (h >= 1) {

            for (int i = h; i < nums.length; i++) {
                int num = nums[i];
                int j = i;
                for (; j > 0 && nums[j - h] > num; j -= h) {
                    nums[j] = nums[j - h];
                }
                nums[j] = num;
            }
            h /= 3;
        }
    }
}
